home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
ftp.cs.arizona.edu
/
ftp.cs.arizona.edu.tar
/
ftp.cs.arizona.edu
/
icon
/
newsgrp
/
group99a.txt
/
000122_icon-group-sender _Fri Jun 4 08:01:40 1999.msg
< prev
next >
Wrap
Internet Message Format
|
2000-09-20
|
4KB
Return-Path: <icon-group-sender>
Received: (from root@localhost)
by baskerville.CS.Arizona.EDU (8.9.1a/8.9.1) id IAA19355
for icon-group-addresses; Fri, 4 Jun 1999 08:01:01 -0700 (MST)
Message-Id: <199906041501.IAA19355@baskerville.CS.Arizona.EDU>
Delivered-To: icon-group@silliac.cs.arizona.edu
From: swampler@noao.edu (Steve Wampler)
Date: Thu, 3 Jun 1999 21:17:38 MST
To: icon-group@optima.CS.Arizona.EDU
Subject: Re: Find the longest matching substrings
Errors-To: icon-group-errors@optima.CS.Arizona.EDU
Status: RO
On Jun 3 at 4:59pm, de yang writes:
} Dear Sirs,
}
} I am working on a project that will mark the inserted or deleted phases
} between two strings. I am wondering whether you know any library
} procedure that will anchor ( or report ) the longest phases that exists
} in both strings.
}
} For example, assume that we have two strings:
} old:="other strings ab cd e and more substrings"
} new:="some more substrings ab cd ab cd e"
}
} This function should return phases and position in both strings, i.e.
} [15, 28, "ab cd e"] for "ab cd e" is the longest phase that matched (
} it has three continuous matching elements ).
I've send a solution to De Yang, but it occurred to me that others
might like to see it (and improve on it - it's a bit, uh, ugly).
This solutions makes two assumptions:
(1) There is a simple definition for what a phrase element is
(in fact, it assumes an element is a sequence of letters!)
(2) Punctuation should be considered when matching phrases, so
"that that is is that that is not is not" and
"that that is, is. that that is not, is not." do not
match each other (instead, the longest common phrase in
this case is "that that is not")
I have another solution that drops assumption 2, if any one is
interested.
Anyway, here's a solution, plus a simple test driver...
-----
procedure main(args)
if result := longPhrase(read(),read()) then
write("[",result[1],",",result[2],",\"",result[3],"\"]")
end
# Find longest phrase common to s1 and s2. Fails if no common phrase.
#
# Assumes simple definition for a phrase (sequence of letters)
# Assumes punctuation is to be considered when matching phrases
#
procedure longPhrase(s1,s2)
static pChars
initial pChars := &letters # chars legal in phrase element
maxlen := 0
every j := findPhrase(s1[ (i := pStart(s1,pChars)) :
(k := rpStop(s1,pChars)) ], s2, pChars) do {
if maxlen <:= numPhrases(s1[i:k], pChars) then {
write(s1[i:k])
saveStart1 := i
saveStop1 := k
saveStart2 := j
}
}
return [\saveStart1, saveStart2, s1[saveStart1:saveStop1]]
end
procedure pStart(s, pc) # generate start of all phrases in s
s ? {
while tab(i := upto(pc)) do {
tab(many(pc))
suspend i
}
}
end
procedure rpStop(s, pc) # generates end of all phrases in s,
# starting from right of string
suspend *s+2 - pStart(reverse(s), pc)
end
procedure numPhrases(s, pc) # Count number of phrases in s
local count
count := 0
every pStart(s,pc) do count +:= 1
return count
end
procedure findPhrase(p, s, pc) # find phrase p in s
s ? {
while tab(i := upto(pc)) do {
if match(p) then suspend i
tab(many(pc))
}
}
end
--
--
Steve Wampler- SOLIS Project, National Solar Observatory
swampler@noao.edu